package com.wxg.algorithm.chapter04;

import java.util.Random;

public class MaxHeap<T extends Comparable> {

    private T[] data;

    private int capacity;

    private int count;

    public MaxHeap(int capacity){
        this.capacity = capacity;
        data = (T[]) new Comparable[capacity + 1]; // 二叉堆-索引从`1`开始
        count = 0;
    }

    public MaxHeap(T[] arr){
        int len = arr.length;
        data = (T[]) new Comparable[len+1];
        capacity = len;
        for (int i=0; i<len; i++){
            data[i+1] = arr[i];
        }
        count = len;

        for (int i=count/2; i>=1; i--){
            shiftDown(i);
        }
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return count == 0;
    }

    public void insert(T item){
        if(count+1 > capacity){
            throw new RuntimeException("超出容量");
        }
        data[count+1] = item;
        count++;
        shiftUp( count );
    }

    public T extractMax(){
        if(count <= 0){
            throw new RuntimeException("已经没有元素了");
        }
        T ret = data[1];

        swap(data, 1, count);
        count --;

        shiftDown(1);

        return ret;
    }

    private void shiftDown(int k) {
        while ( 2*k <= count ){
            int j = 2*k; //
            if( j + 1 <= count && data[j+1].compareTo(data[j]) > 0 ){
                j += 1;
            }

            if( data[k].compareTo(data[j]) > 0 ){ // 这里`==0`时也可以break吧?
                break;
            }

            swap(data, k, j);
            k = j;
        }
    }

    private void shiftUp(int k) {
        while ( k > 1 && data[k/2].compareTo(data[k]) < 0){
            swap(data, k/2, k);
            k /= 2;
        }
    }

    private void swap(T[] arr, int a, int b) {
        T temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        Random rand = new Random();

        MaxHeap<Integer> maxHeap = new MaxHeap<>(100);
        System.out.println(maxHeap.size());

        for (int i = 0; i < 30; i++){
            maxHeap.insert(rand.nextInt(100));
        }

        while (!maxHeap.isEmpty()){
            System.out.print(maxHeap.extractMax() + " ");
        }
        System.out.println();
    }
}
